#include"SeqList.h"

void SeqListInit(SL* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SeqListPushFront(SL* ps, IntSeqList x)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int New_Capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SL* ptr = (SL*)realloc(ps->data, sizeof(SL) * New_Capacity);
		if (ptr == NULL)
		{
			perror("realloc fail::");
			exit(-1);
		}
		ps->data = ptr;
		ps->capacity = New_Capacity;
	}
	ps->data[ps->size++] = x;
}
void SeqList_Draw_(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}
void SeqList_PopBack_(SL* ps)
{
	assert(ps && ps->size >= 0);
	for (int start = 0; start < ps->size; start++)
	{
		IntSeqList tmp = ps->data[start];
		ps->data[start] = ps->data[start + 1];
		ps->data[start + 1] = tmp;
	}
	ps->size--;

}
void SeqList_PushBack_(SL* ps, IntSeqList x)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int New_Capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SL* ptr = (SL*)realloc(ps->data, sizeof(SL) * New_Capacity);
		if (ptr == NULL)
		{
			perror("realloc fail::");
			exit(-1);
		}
		ps->data = ptr;
		ps->capacity = New_Capacity;
	}
	for (int end = ps->size; end > 0; end--)
	{
		IntSeqList tmp = ps->data[end];
		ps->data[end] = ps->data[end - 1];
		ps->data[end - 1] = tmp;
	}
	ps->data[0] = x;
	ps->size++;
}
void SeqList_InsertFront(SL* ps, int pos, IntSeqList x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	if (ps->size == ps->capacity)
	{
		int New_Capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SL* ptr = (SL*)realloc(ps->data, sizeof(SL) * New_Capacity);
		if (ptr == NULL)
		{
			perror("realloc fail::");
			exit(-1);
		}
		ps->data = ptr;
		ps->capacity = New_Capacity;
	}
	if (pos == 0)
	{
		SeqList_PushBack_(ps, x);
		return;
	}
	if (pos == ps->size)
	{
		SeqListPushFront(ps, x);
		return;
	}
	for (int i = ps->size; i > pos; i--)
	{
		IntSeqList tmp = ps->data[i];
		ps->data[i] = ps->data[i - 1];
		ps->data[i - 1] = tmp;
	}
	ps->data[pos] = x;
	ps->size++;
}
void SeqList_PopInsertFront_(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	if (pos == 0)
	{
		SeqList_PopBack_(ps);
		return;
	}
	if (pos == ps->size - 1)
	{
		SeqList_PopFront_(ps);
		return;
	}
	for (int i = pos; i < ps->size; i++)
	{
		IntSeqList tmp = ps->data[i];
		ps->data[i] = ps->data[i + 1];
		ps->data[i + 1] = tmp;
	}
}
void SeqList_PopFront_(SL* ps)
{
	assert(ps && ps->size > 0);

	ps->size--;
}
void SeqListDesty(SL* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

int  SeqList_Min(SL* ps) {
	assert(ps);
	int pos = 0;
	int Min = ps->data[0];
	for (int i = 1; i < ps->size; i++)
	{
		if (ps->data[i] < Min)
		{
			Min = ps->data[i];
			pos = i;
		}
	}
	for (int i = pos; i < ps->size; i++)
	{
		int tmp = ps->data[i];
		ps->data[i] = ps->data[i + 1];
		ps->data[i + 1] = tmp;
	}
	ps->data[ps->size] = Min;
	return Min;
}
void SeqList_Resever(SL* ps)
{
	assert(ps);
	int left = 0;
	int right = ps->size - 1;
	while (left < right)
	{
		int tmp = ps->data[left];
		ps->data[left] = ps->data[right];
		ps->data[right] = tmp;
		left++;
		right--;
	}

}
void SeqList_repeat(SL* ps, IntSeqList x)
{
	assert(ps);
	int start = 0;
	int dest = 0;
	while (dest < ps->size)
	{
		if (ps->data[dest] != x)
		{
			ps->data[start] = ps->data[dest];
			start++;
			dest++;
		}
		dest++;
	}
}
void SeqList_DeleteOrder(SL* ps, int start, int end)
{
	assert(ps);
	assert(start >= 0 && end < ps->size);
	if (start == 0 && end == ps->size - 1)
	{
		ps->size == 0;
		exit(-1);
	}
	while (end < ps->size - 1)
	{

		ps->data[start] = ps->data[end + 1];
		start++;
		end++;

	}
	ps->size = start;
}

void SeqList_PopOver(SL* ps)
{
	assert(ps);

}
int SeqList_removeDuplicates(int* nums, int numsSize)
{
	assert(nums);
	int slow = 0;
	int flast = 0;
	while (flast < numsSize)
	{
		if (nums[slow] != nums[flast])
		{
			slow++;
			nums[slow] = nums[flast];

			flast++;
		}
		else
		{
			flast++;
		}
	}
	return slow + 1;
}
void SeqList_Exchange(SL* ps1, SL* ps2)
{
	assert(ps1 && ps2);
	int* ptr = (int*)malloc(sizeof(int) * (ps1->size + ps2->size));
	if (ptr == NULL)
	{
		perror("malloc file::");
		return;
	}
	int start = 0;
	int dest = 0;
	int i;
	for (i = 0; i < ps1->size + ps2->size; i++)
	{
		if (start < ps1->size && dest < ps2->size)
		{
			if (ps1->data[start] > ps2->data[dest])
			{
				*(ptr + i) = ps1->data[start];
				start++;
			}
			else
			{
				*(ptr + i) = ps2->data[dest];
				dest++;
			}
		}
	}
	if (start == ps1->size) {
		memcpy(ptr+i-1, ps2->data + dest, (ps2->size - dest) * sizeof(int));
	}
	if (dest == ps2->size)
	{
		memcpy(ptr+i-1, ps1->data + start, (ps1->size - start) * sizeof(int));
	}
	for (int i = 0; i < ps1->size + ps2->size; i++)
	{
		printf("%d ", *(ptr + i));
	}
	free(ptr);
	ptr = NULL;
}
void SeqList_Find_certain(SL* ps, IntSeqList x)
{
	assert(ps);
	int i;
	for ( i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
		{
			int tmp = ps->data[i];
			ps->data[i] = ps->data[i + 1];
			ps->data[i + 1] = tmp;
			return;
		}
	}
	int pos = 0;
	for (int j = 0; j < ps->size; j++)
	{
		if (ps->data[j] < x)
		{
			if (ps->size == ps->capacity)
			{
				int New_Capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
				SL* ptr = (SL*)realloc(ps->data, sizeof(SL) * New_Capacity);
				if (ptr == NULL)
				{
					perror("realloc fail::");
					exit(-1);
				}
				ps->data = ptr;
				ps->capacity = New_Capacity;
			}
			pos = j;
			for (int k = ps->size; k > j; k--)
			{
				int tmp = ps->data[k];
				ps->data[k] = ps->data[k - 1];
				ps->data[k - 1] = tmp;
			}
			ps->data[pos] = x;
			return;

		}
		
	}
	
}
void SeqList_Find_certain2(SL* ps, IntSeqList x)
{
	assert(ps);
	int left = 0;
	int right = ps->size-1;
	int mid = 0;
	while (left <= right)
	{
		 mid = (left + right) / 2;
		if (ps->data[mid] > x)
		{
			left = mid + 1;
		}
		else if (ps->data[mid] < x)
		{
			
			right = mid - 1;
		}
		else
		{
			break;
		}
		
	}
	if (ps->data[mid] == x)
	{
		int tmp = ps->data[mid];
		ps->data[mid] = ps->data[mid + 1];
		ps->data[mid+1] = tmp;
	}
	else
	{
		if (ps->data[mid] > x)
		{
			for (int i = ps->size; i > mid+1; i--)
			{
				int tmp = ps->data[i];
				ps->data[i] = ps->data[i - 1];
				ps->data[i - 1] = tmp;

			}
			ps->data[mid+1] = x;
			ps->size++;
		}
		else
		{
			for (int i =ps->size; i > mid; i--)
			{
				int tmp = ps->data[i];
				ps->data[i] = ps->data[i - 1];
				ps->data[i - 1] = tmp;

			}
			ps->data[mid] = x;
			ps->size++;
		}
	}
	
}
void revolve(IntSeqList*data, int len)
{
	int start = 0;
	int dest = len;
	while (start < dest)
	{
		int tmp = data[start];
		data[start] = data[dest];
	    data[dest] = tmp;
		start++;
		dest--;
	}
}
void SeqList_revolve(SL* ps, IntSeqList k)
{
	assert(ps);
	revolve(ps->data,ps->size-1);
	revolve(ps->data, k-1);
	revolve(ps->data+k, ps->size - k-1);
}
void SeqList_Median(SL* ps1, SL* ps2)
{
	assert(ps1 && ps2);
	assert(ps1 && ps2);
	int* ptr = (int*)malloc(sizeof(int) * (ps1->size + ps2->size));
	if (ptr == NULL)
	{
		perror("malloc file::");
		return;
	}
	int start = 0;
	int dest = 0;
	int i; int j = 0;
	for (i = 0; i < ps1->size + ps2->size; i++)
	{
		if (start < ps1->size && dest < ps2->size)
		{
			if (ps1->data[start] > ps2->data[dest])
			{
				*(ptr + i) = ps1->data[start];
				j++;
				start++;
			}
			else
			{
				*(ptr + i) = ps2->data[dest];
				j++;
				dest++;
			}
		}
	}
	if (start == ps1->size) {
		memcpy(ptr +j-1, ps2->data + dest, (ps2->size - dest) * sizeof(int));
	}
	if (dest == ps2->size)
	{
		memcpy(ptr + j - 1, ps1->data + start, (ps1->size - start) * sizeof(int));
	}
	int flast = 0;
	int slow = 0;
	while (flast<sizeof(ptr))
	{
		flast = flast + 2;
		slow = slow + 1;

	}
	printf("%d\n", *(ptr + slow));
	free(ptr);
	ptr = NULL;
     
}
void SeqList_Element(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		for (int j = 0; j < ps->size - i - 1; j++)
		{
			if (ps->data[j] > ps->data[j + 1])
			{
				int tmp = ps->data[j];
				ps->data[j] = ps->data[j + 1];
				ps->data[j + 1] = tmp;
			}
		}
	}
	int start = 0;
	int end = 0;
	int count = 1;
	int len = ps->size / 2;
	while (end < ps->size)
	{
		end++;
		if (ps->data[start] == ps->data[end])
		{
			count++;
			if (count == len) {
				printf("%d\n", ps->data[start]);
				return;
			}
		}
		else
		{
			start = end;
			count = 1;
		}
	}
	printf("%d\n", -1);
}